#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode * _dummyHead = new ListNode(0);
        ListNode * cur = _dummyHead;
        ListNode * cur1 = l1;
        ListNode * cur2 = l2;
        int carry = 0;
        int num = 0;
        while(cur1 != nullptr || cur2 != nullptr)
        {
            if(cur1 == nullptr)
            {
                num = (cur2->val + carry) % 10;
                carry = (cur2->val + carry) / 10;
                cur2 = cur2->next;
            }
            else if(cur2 == nullptr)
            {
                num = (cur1->val + carry) % 10;
                carry = (cur1->val + carry) / 10;
                cur1 = cur1->next;
            }
            else
            {
                num = (cur1->val + cur2->val + carry) % 10;
                carry = (cur1->val + cur2->val + carry) / 10;
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            cur->next = new ListNode(num);
            cur = cur->next;
        }
        if(carry)
        {
            cur->next = new ListNode(carry);
            cur = cur->next;
        }
        ListNode * result = _dummyHead->next;
        delete _dummyHead;
        return result;
    }
};

// 辅助函数：从vector创建链表（逆序存储）
ListNode* createList(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    
    for (int i = 1; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    cout << "[";
    while (cur != nullptr) {
        cout << cur->val;
        if (cur->next != nullptr) cout << ",";
        cur = cur->next;
    }
    cout << "]";
}

// 辅助函数：将链表转换为实际数字（用于验证，仅适用于小数字）
long long listToNumber(ListNode* head) {
    long long result = 0;
    long long multiplier = 1;
    ListNode* cur = head;
    while (cur != nullptr) {
        result += cur->val * multiplier;
        multiplier *= 10;
        cur = cur->next;
    }
    return result;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution solution;
    
    // 测试案例1：题目示例 [2,4,3] + [5,6,4] = [7,0,8]
    cout << "测试案例1: ";
    vector<int> nums1_1 = {2, 4, 3}; // 表示342
    vector<int> nums1_2 = {5, 6, 4}; // 表示465
    ListNode* l1_1 = createList(nums1_1);
    ListNode* l1_2 = createList(nums1_2);
    cout << "l1 = ";
    printList(l1_1);
    cout << " (表示 " << listToNumber(l1_1) << ")";
    cout << ", l2 = ";
    printList(l1_2);
    cout << " (表示 " << listToNumber(l1_2) << ")";
    ListNode* result1 = solution.addTwoNumbers(l1_1, l1_2);
    cout << " -> ";
    printList(result1);
    if (result1) cout << " (表示 " << listToNumber(result1) << ")";
    cout << " (期望: [7,0,8] 表示 807)" << endl;
    deleteList(result1);
    
    // 测试案例2：[0] + [0] = [0]
    cout << "测试案例2: ";
    vector<int> nums2_1 = {0};
    vector<int> nums2_2 = {0};
    ListNode* l2_1 = createList(nums2_1);
    ListNode* l2_2 = createList(nums2_2);
    cout << "l1 = ";
    printList(l2_1);
    cout << ", l2 = ";
    printList(l2_2);
    ListNode* result2 = solution.addTwoNumbers(l2_1, l2_2);
    cout << " -> ";
    printList(result2);
    cout << " (期望: [0])" << endl;
    deleteList(result2);
    
    // 测试案例3：[9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    cout << "测试案例3: ";
    vector<int> nums3_1 = {9, 9, 9, 9, 9, 9, 9}; // 表示9999999
    vector<int> nums3_2 = {9, 9, 9, 9}; // 表示9999
    ListNode* l3_1 = createList(nums3_1);
    ListNode* l3_2 = createList(nums3_2);
    cout << "l1 = ";
    printList(l3_1);
    cout << ", l2 = ";
    printList(l3_2);
    ListNode* result3 = solution.addTwoNumbers(l3_1, l3_2);
    cout << " -> ";
    printList(result3);
    cout << " (期望: [8,9,9,9,0,0,0,1])" << endl;
    deleteList(result3);
    
    // 测试案例4：[1] + [9,9] = [0,0,1]
    cout << "测试案例4: ";
    vector<int> nums4_1 = {1}; // 表示1
    vector<int> nums4_2 = {9, 9}; // 表示99
    ListNode* l4_1 = createList(nums4_1);
    ListNode* l4_2 = createList(nums4_2);
    cout << "l1 = ";
    printList(l4_1);
    cout << ", l2 = ";
    printList(l4_2);
    ListNode* result4 = solution.addTwoNumbers(l4_1, l4_2);
    cout << " -> ";
    printList(result4);
    cout << " (期望: [0,0,1] 表示 100)" << endl;
    deleteList(result4);
    
    // 测试案例5：[5] + [5] = [0,1]
    cout << "测试案例5: ";
    vector<int> nums5_1 = {5}; // 表示5
    vector<int> nums5_2 = {5}; // 表示5
    ListNode* l5_1 = createList(nums5_1);
    ListNode* l5_2 = createList(nums5_2);
    cout << "l1 = ";
    printList(l5_1);
    cout << ", l2 = ";
    printList(l5_2);
    ListNode* result5 = solution.addTwoNumbers(l5_1, l5_2);
    cout << " -> ";
    printList(result5);
    cout << " (期望: [0,1] 表示 10)" << endl;
    deleteList(result5);
    
    // 测试案例6：[1,8] + [0] = [1,8]
    cout << "测试案例6: ";
    vector<int> nums6_1 = {1, 8}; // 表示81
    vector<int> nums6_2 = {0}; // 表示0
    ListNode* l6_1 = createList(nums6_1);
    ListNode* l6_2 = createList(nums6_2);
    cout << "l1 = ";
    printList(l6_1);
    cout << ", l2 = ";
    printList(l6_2);
    ListNode* result6 = solution.addTwoNumbers(l6_1, l6_2);
    cout << " -> ";
    printList(result6);
    cout << " (期望: [1,8] 表示 81)" << endl;
    deleteList(result6);
    
    return 0;
}